Міністерство освіти і науки, молоді та спорту України
Національний Університет «Львівська Політехніка»
кафедра АСУ
Звіт
до лабораторної роботи №9
на тему: «НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. ЗАДАЧІ ДРОБОВО-ЛІНІЙНОГО ПРОГРАМУВАННЯ»
з дисципліни:
«Математичні методи дослідження операцій»
Лабораторна робота №9
«НЕЛІНІЙНЕ ПРОГРАМУВАННЯ. ЗАДАЧІ ДРОБОВО-ЛІНІЙНОГО ПРОГРАМУВАННЯ»
Короткі теоретичні відомості
Геометрична інтерпретація задачі дробово-лінійного програмування
У разі, коли задача дробово-лінійного програмування містить лише дві змінні, для її розв’язування зручно скористатися графічним методом.
Нехай маємо таку задачу:
/ (1.4)
за умов:
/ (1.5)
/, / (1.6)
Спочатку, як і для звичайної задачі лінійного програмування будуємо геометричне місце точок системи нерівностей (1.5), що визначає деякий багатокутник допустимих розв’язків.
Допустимо, що /, і цільова функція набуває деякого значення:
/.
Після елементарних перетворень дістанемо:
/ або /. (1.7)
Останнє рівняння описує пряму, що обертається навколо початку системи координат залежно від зміни значень х1 та х2.
Розглянемо кутовий коефіцієнт нахилу прямої (1.7), що виражає цільову функцію:
/. (1.8)
Отже, кутовий коефіцієнт є функцію від Z.
Для визначення умов зростання (спадання) функції (1.8) дослідимо зміну знака її похідної:
/(1.9)
Використовуючи формулу (1.9), можна встановити правила пошуку максимального (мінімального) значення цільової функції:
а) якщо /, то функція (1.8) є зростаючою, і при збільшенні значення Z (значення цільової функції) кутовий коефіцієнт нахилу прямої (1.7) також збільшується. Тому у разі, якщо /, то для відшукання точки максимуму необхідно повертати пряму, що описує цільову функцію, навколо початку системи координат у напрямку проти годинникової стрілки;
б) якщо /, то функція (1.8) є спадною, і при збільшенні значення Z (значення цільової функції) кутовий коефіцієнт нахилу прямої (1.7) зменшується. Тому у разі, якщо /, то для відшукання точки максимуму необхідно повертати пряму, що описує цільову функцію, навколо початку системи координат у напрямку за годинниковою стрілкою.
При розв’язуванні задачі дробово-лінійного програмування графічним методом можливі такі випадки:
- багатокутник розв’язків задачі обмежений, - і максимальне та мінімальне значення досягаються у його кутових точках;
- багатокутник розв’язків задачі необмежений, - однак існують кутові точки, в яких досягаються максимальне та мінімальне значення цільової функції;
- багатокутник розв’язків задачі необмежений, - і досягається лише один із екстремумів;
- багатокутник розв’язків задачі необмежений, - і точки екстремумів визначити неможливо.
Приклад 1.1 Розв’яжемо графічно задачу дробово-лінійного програмування:
/ за умов: / /.
Розв’язання. Побудуємо на площині область допустимих розв’язків задачі. Маємо трикутник АВС. /
Рис. 1.1
Цільова функція задачі - це пряма, що обертається навколо початку системи координат (на рис. 1.1 позначена пунктиром). Отже, залежно від напрямку обертання точками максимуму та мінімуму будуть відповідно точки А і С.
Скористаємося правилами визначення максимального та мінімального значень цільової функції. Перевіримо умову
/,
тобто для будь-якого значення Z функція / є спадною.
Отже, зі зростанням Z кутовий коефіцієнт нахилу прямої, що виражає цільову функцію, зменшуватиметься, а тому відповідну пряму потрібно обертати навколо початку координат за годинниковою стрілкою.
Виконуючи зазначений порядок дій, маємо: С — точка максимуму, а точка А є точкою мінімуму цієї задачі.
Розв’язування дробово-лінійної задачі зведенням до задачі лінійного програмування
Нехай потрібно розв’язати задачу (1.1)—(1.3).
Позначимо
/ ...
